#include<stdio.h>
#include<stdlib.h>




typedef struct Poly{//多项式的每一项的结构
    double xishu;//系数
    int index;//指数
    struct Poly *next;//结构体指针
}node,*Node;






Node Create_Poly();
void Sortpoly();
void Displaypoly();
void Add_Sub();
void Mult();

int count;//多项式操作选择




#include<stdio.h>
#include<stdlib.h>
#include"struct.h"
#include"head.h"
Node node,*Node;
int count;//多项式操作选择
Node Create_Poly(){//建立多项式
    Node head = NULL;
    Node p1,p2=NULL;
    int n;//项数
    int i;
    count++;
    printf(" 请输入多项式");
    if(count==1)printf(" A ");
    else printf(" B ");
    printf("的项数");
    scanf("%d",&n);
    head = (Node)malloc(sizeof(node));//创建动态链表
    for(i=1;i<=n;i++){//根据项数n创建多项式链表
        if((p1=(Node)malloc(sizeof(node)))==NULL){
            printf("内存不足空间申请失败");
            exit(0);
        }
        p1->next = NULL;
        printf("请输入多项式");
        if(count==1){
        printf(" A ");
        }
        else{
        printf(" B ");
        }
        printf("的第 %d 项系数和指数： ",i);
        scanf("%lf",&p1->xishu);
        scanf("%d",&p1->index);
        if(i==1){head->next = p1;}
        //输入是第一项时，头结点指向第一项
        else{
        p2->next = p1;//连接链表
        }
        p2 = p1;//置换p1 p2 使用尾插法建立多项式 p2始终指向最后一项
    }
    printf(" 多项式");
    if(count==1)
    printf(" A = ");
    else 
    printf(" B = ");
    Sortpoly(head);
    Displaypoly(head);
    printf("------------------------------\n");
    return head;
}



#include<stdio.h>
#include<stdlib.h>
#include"struct.h"
#include"head.h"
Node node,*Node;
int count;//多项式操作选择


void Sortpoly(Node head){//整理按指数大小将多项式各项降序排序
Node p1,curr,pre,p2 = NULL;//新建链表
    p1 = head->next;//p1指针指向的结点逐个取出作为插入结点
    head->next = NULL;//head头结点置空
    while(p1 != NULL){//多项式非空时循环
        curr = head->next;
        pre = head;//定位插入位置，退出循环时pre要指向要插入节点的位置
        while(curr != NULL && curr->index >= p1->index){
            pre = curr;
            curr = curr->next;
        }
        p2 = p1;//p2指针指向要插入节点位置
        p1 = p1->next;//p1指针指向下一个节点
        p2->next = pre->next;//p指针所指结点插入pre指针所指结点后
        pre->next = p2;
    }
}



#include<stdio.h>
#include<stdlib.h>
#include"struct.h"
#include"head.h"
Node node,*Node;
int count;//多项式操作选择


void Displaypoly(Node head){//输出函数
Node p =NULL;//初始化指针
    int i;
    for(p=head->next,i=0;p!=NULL;p=p->next,i++){//当链表不为空时执行循环
        if(p->index == 0){//指数为零时打印常数
            if(p->xishu == 0)break;
            else printf("%.2f",p->xishu);
        }
        else if(p->index == 1){//指数为一时
            if(p->xishu==1)
            printf("x");
            else if(p->xishu == -1)
            printf("-x");
            else printf("%.2lfx",p->xishu);
        }
        else if(p->index!=1){//指数不唯一时分情况讨论输出情况
            if(p->xishu==1&&p->index>0)
            printf("x^%d",p->index);
			else if(p->xishu==-1&&p->index>0)
            printf("-x^%d",p->index);
			else if(p->xishu==1&&p->index<0)
            printf("x^(%d)",p->index);
			else if(p->xishu==-1&&p->index<0)
            printf("-x^(%d)",p->index);
			else if(p->index<0)
            printf("%.2lfx^(%d)",p->xishu,p->index);
			else 
            printf("%.2lfx^%d",p->xishu ,p->index);
        }
        if(p->next != NULL && p->next->xishu > 0)//各项之间使用+号相连
        printf("+");
    }
    if(i==0)//若多项式运算结果使链表为空则输出0
    printf("0.00");
    printf("\n");
}




#include<stdio.h>
#include<stdlib.h>
#include"struct.h"
#include"head.h"
Node node,*Node;
int count;//多项式操作选择


void Add_Sub(Node head1,Node head2)//对A，B多项式进行加减操作
{
	Node head=NULL;//新建链表储存相加后多项式
	Node p1=NULL;//中间变量
	Node p2=NULL;//保留前一个结点
	Node p=NULL;//第一个多项式的循环变量
	Node pp=NULL;//第二个多项式的循环变量
	if((head=(Node)malloc(sizeof(node)))==NULL){
		printf("内存不足空间分配失败");
		exit(0);
	}
	head->next=NULL;
	for(pp=head2->next;pp!=NULL;pp=pp->next){//复制第二个多项式链表
		if((p1=(Node)malloc(sizeof(node)))==NULL){
			printf("内存不足空间分配失败");
			exit(0);
		}
		p1->next=NULL;
		if(count==2)p1->xishu=pp->xishu;//加法直接复制
		if(count==3||count==4)p1->xishu=(-1.0)*pp->xishu;//减法取相反数
		p1->index=pp->index;
		if(head->next==NULL)head->next=p1;
		else p2->next=p1;
		p2=p1;
	}
	for(p=head1->next;p!=NULL;p=p->next){//循环多项式的每一项
		for(pp=head->next,p2=head; pp!=NULL; ){
			if(p->index == pp->index){//指数项等
				pp->xishu=p->xishu+pp->xishu;//系数相加
				if(pp->xishu==0){
					pp=pp->next;
					p2->next=pp;
				}
				else{
					pp=pp->next;
					p2=p2->next;
				}
				break;
			}
			if(pp->next==NULL){//没有相同指数项，创建添加
				if((p1=(Node)malloc(sizeof(node)))==NULL){
					printf("内存不足空间分配失败");
					exit(0);
				}
				p1->next =NULL;
				p1->xishu=p->xishu;//多余项添加到新建链表
				p1->index=p->index;
				p1->next=head->next;
				head->next=p1;
				pp=pp->next;
				p2=p2->next;
				break;
			}
			pp=pp->next;
			p2=p2->next;
		}
	}
	if(count==2)printf(" A + B = ");
	if(count==3)printf(" A - B = ");
	if(count==4)printf(" B - A = ");
	Sortpoly(head);
	Displaypoly(head);
	printf(" -----------------------------------\n");
}





#include<stdio.h>
#include<stdlib.h>
#include"struct.h"
#include"head.h"
Node node,*Node;
int count;//多项式操作选择


void Mult(Node head1,Node head2){
Node head = NULL;//相乘后的存储多项式所有式的链表头结点
Node p1=NULL;//中间变量
Node p2=NULL;//保留前一个结点
Node p=NULL;//第一个多项式的循环变量
Node pp=NULL;//第二个多项式的循环变量
    if((head=(Node)malloc(sizeof(node)))==NULL){
        printf("内存不足空间分配失败");
        exit(0);
    }
    head->next=NULL;//两个循环建立多项式相乘后所有相的存储链表
    for(p=head1->next;p!=NULL;p=p->next){
        for(pp=head2->next;pp!=NULL;pp=pp->next){
            if((p1=(Node)malloc(sizeof(node)))==NULL){
                printf("内存不足空间分配失败");
                exit(0);
            }
            p1->next=NULL;
            p1->xishu=p->xishu*pp->xishu;//系数相乘
            p1->index=p->index+pp->index;//指数相加
            if(head->next==NULL)
            head->next=p1;
            else
            {
                p2->next=p1;
            }
            p2=p1;//p2始终指向尾结点
            
            
        }
    }
    for(p=head->next;p!=NULL;p=p->next){//合并多项式，相同指数项合并
        for(pp=p->next,p2=p;pp!=NULL;pp=pp->next,p2=p2->next){
            if(p->index==pp->index){
                p->xishu=p->xishu+pp->xishu;
                pp=pp->next;
                p2->next=pp;
            }
        }
    }
    if(count==5)printf(" A * B = ");
    Sortpoly(head);//重新指数降序排序相乘后的链表
    Displaypoly(head);//输出结果多项式
    printf("----------------------------\n");
}






#include<stdio.h>
#include<stdlib.h>
#include"struct.h"
#include"head.h"
Node node,*Node;
int count;//多项式操作选择

void main(){
    int choice,i=0;
    Node head1=NULL;
	Node head2=NULL;
    do{
        system("cls");
        printf("\n");
        printf("|-----------20191331一元稀疏多项式-------------| \n");
        printf("|-------------   1——建立A、B多项式  ---------- | \n");
        printf("|---------------   2——加法 A+B  --------------| \n");
        printf("|--------  3——减法 A-B    4——减法 B-A  --------| \n");
        printf("|---------------   5——乘法 A*B  ---------------| \n");
        printf("|---------------   0——退出程序  ----------------| \n");
        printf("|----------------------------------------------| \n");
        printf(" 请输入您的选择 ： ");
        scanf("%d",&choice);
        printf("----------------------------\n");
        switch(choice){
            case 0:break;
            case 1:{
                count = 0;
                head1 = Create_Poly();
                head2 = Create_Poly();
                system("pause");
                break;
            }
            case 2:{
                if(head1==NULL){
                    count=0;
                    printf("A多项式不存在 \n");
                    head1= Create_Poly();
                }
                if(head2==NULL){
                    count=1;
                    printf("B多项式不存在 \n");
                    head2= Create_Poly();
                }
                count=2;
                printf(" 多项式 A = ");
                Displaypoly(head1);
                printf(" 多项式 B = ");
                Displaypoly(head2);
                Add_Sub(head1,head2);
                system("pause");
                break;
            }
            case 3:{
                if(head1==NULL){
                    count=0;
                    printf("A多项式不存在 \n");
                    head1= Create_Poly();
                }
                if(head2==NULL){
                    count=1;
                    printf("A多项式不存在 \n");
                    head2= Create_Poly();
                }
                count=3;
                printf(" 多项式 A = ");
				Displaypoly(head1);
				printf(" 多项式 B = ");
				Displaypoly(head2);
				Add_Sub(head1,head2); 
				system("pause"); 
				break;
            }
            case 4:{
                if(head1==NULL){
                    count=0;
                    printf("A多项式不存在 \n");
                    head1= Create_Poly();
                }
                if(head2==NULL){
                    count=1;
                    printf("A多项式不存在 \n");
                    head2= Create_Poly();
                }
                count=4;
                printf(" 多项式 A = ");
				Displaypoly(head1);
				printf(" 多项式 B = ");
				Displaypoly(head2);
				Add_Sub(head2,head1); 
				system("pause"); 
				break;
            }
            case 5:{
                if(head1==NULL){
                    count=0;
                    printf("A多项式不存在 \n");
                    head1= Create_Poly();
                }
                if(head2==NULL){
                    count=1;
                    printf("B多项式不存在 \n");
                    head2= Create_Poly();
                }
                count=5;
                printf(" 多项式 A = ");
				Displaypoly(head1);
				printf(" 多项式 B = ");
				Displaypoly(head2);
				Mult(head1,head2); 
				system("pause"); 
				break;
            }
        }
       
    }while (choice);
}